package com.zs.letcode.top_interview_questions;

import java.util.Arrays;

/**
 * 大数
 * 给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
 * <p>
 * 注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums = [10,2]
 * 输出："210"
 * 示例2：
 * <p>
 * 输入：nums = [3,30,34,5,9]
 * 输出："9534330"
 * 示例 3：
 * <p>
 * 输入：nums = [1]
 * 输出："1"
 * 示例 4：
 * <p>
 * 输入：nums = [10]
 * 输出："10"
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= nums.length <= 100
 * 0 <= nums[i] <= 109
 * 相关标签
 * 排序
 * <p>
 * Python3
 * <p>
 * <p>
 * <p>
 * 作者：力扣 (LeetCode)
 * 链接：https://leetcode-cn.com/leetbook/read/top-interview-questions/xa1401/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/6/10 08:40
 */
public class Chapter49 {
    public static void main(String[] args) {

    }

    private class Solution {
        public String largestNumber(int[] nums) {
            int n = nums.length;
            // 转换成包装类型，以便传入 Comparator 对象（此处为 lambda 表达式）
            Integer[] numsArr = new Integer[n];
            for (int i = 0; i < n; i++) {
                numsArr[i] = nums[i];
            }
            Arrays.sort(numsArr, (x, y) -> {
                long sx = 10, sy = 10;
                while (sx <= x) {
                    sx *= 10;
                }
                while (sy <= y) {
                    sy *= 10;
                }
                return (int) (-sy * x - y + sx * y + x);
            });
            if (numsArr[0] == 0) {
                return "0";
            }
            StringBuilder ret = new StringBuilder();
            for (int num : numsArr) {
                ret.append(num);
            }
            return ret.toString();
        }

        public String largestNumber1(int[] nums) {
            int n = nums.length;
            String[] numsToWord = new String[n];
            for (int i = 0; i < n; i++) {
                numsToWord[i] = String.valueOf(nums[i]);
            }
            //compareTo()方法比较的时候是按照ASCII码逐位比较的
            //通过比较(a+b)和(b+a)的大小，就可以判断出a,b两个字符串谁应该在前面
            //所以[3,30,34]排序后变为[34,3,30]
            //[233，23333]排序后变为[23333，233]
            Arrays.sort(numsToWord, (a, b) -> (b + a).compareTo(a + b));
            //如果排序后的第一个元素是0，那后面的元素肯定小于或等于0，则可直接返回0
            if (numsToWord[0].equals("0")) {
                return "0";
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                sb.append(numsToWord[i]);
            }
            return sb.toString();
        }
    }
}
